package algorithm.graph;

/**
 * @author bingo
 * @Description    求图的联通分量
 * @Date 2018/6/20
 */
public class Component {

    private Graph graph;

    private boolean[] visited;

    private int count=0;

    private int[] id;

    public Integer getCount() {
        return count;
    }

    public Component(Graph graph) {
        this.graph = graph;
        visited = new boolean[graph.n()];
        id = new int[graph.n()];
        for(int i=0;i<graph.n();i++){
            visited[i] = false;
            id[i] = -1;
        }
        for(int i = 0;i<graph.n();i++){
            if(!visited[i]){
                dfs(i);
                count++;

            }

        }
    }

    private void dfs(int i) {
        visited[i] = true;
        id[i] = count;
        for(Integer item:graph.adj(i)){
           if(!visited[item]){
               dfs(item);
           }

        }

    }

    public boolean connected(int v, int w){

        return  id[v] == id[w];
    }

    public void printId(){

        for(int i=0;i<id.length;i++){
            System.out.print(id[i]+",");
        }
        System.out.println();
    }

    public static void main(String[] args) {

        ReadGraph readGraph = new ReadGraph();

        Graph sparseGraph = new SparseGraph(13,false);
        readGraph.readGraph(sparseGraph,"demo/component1.txt");
        Component component = new Component(sparseGraph);
        System.out.println("component1图联通分量:"+component.getCount());
        System.out.println(component.connected(4,7));
        component.printId();

        System.out.println("----------------------------------------------------");

        Graph sparseGraph2 = new SparseGraph(6,false);
        readGraph.readGraph(sparseGraph2,"demo/component2.txt");
        Component component2 = new Component(sparseGraph2);
        System.out.println("component2图联通分量:"+component2.getCount());
        component.printId();

        System.out.println("----------------------------------------------------");
        Graph sparseGraph3 = new SparseGraph(7,false);
        readGraph.readGraph(sparseGraph3,"demo/component3.txt");
        Component component3 = new Component(sparseGraph3);
        System.out.println("component3图联通分量:"+component3.getCount());
        component.printId();

    }

}
